小A买了一个新的存钱罐，他很开心。从他买存钱罐的第 1 天起， 他每天都会往存钱罐里存钱， 第 1 天存 1 元， 第 2 天存 2 元…以此类推， 第 i 天存 i 元， 小A想要知道他最早哪一天能存到 N 元以上， 你能帮他算一算吗。

前3个测试点满足

1≤N≤105

后2个测试点满足

1≤N≤109

所有测试点中 T 满足 1≤T≤105

输入格式：

总共有 T 次询问, Ni表示存钱罐中存到Ni元需要多少天

1
2
3
4
5
6
7
8
T
N1
N2
N3
...
Ni
...
NT

输出格式：

输出T个数， 表示最早存到 Ni元以上的天数

输入样例：

1
2
3
2
12
100128

输出样例：

1
2
5
447

对于第一个询问的解释 :

第 1 天存钱罐有 1 元

第 2 天存钱罐有 3 元

第 3 天存钱罐有 6 元

第 4 天存钱罐有 10 元

第 5 天存钱罐有 15 元, 大于 12 元, 因此答案是第 5 天

思路

等差数列an=n，询问该等差数列前n项和，n为几时大于给定的Ni

  1. 可直接暴力循环计算，会超时
  2. 利用等差数列求和公式，Sn=(n*(a1+an))/2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    long n;
    scanf("%ld", &n);
    while(n--) {
        double id;
        scanf("%lf", &id);
        double ret = -(1 - sqrt(1 + 8 * id)) / 2;//根据求和公式推导ret的公式
        if(ret == (long)ret) {
            printf("%ld\n", (long)ret);
        } else {
            printf("%ld\n", (long)ret + 1);
        }
    }
    return 0;
}